package com.wtgroup.demo.mianshi.算法.动态规划.暴力递归;

import com.wtgroup.demo.common.judge.Judger;

/**
 * N 个位置(>=2), 机器人从 M 经过 K 步走到 P,
 * 一共有多少种走法.
 * 一次只能移动一步.
 * 走到最左时, 下一步只能往右, 同理最右, 下一步只能往左.
 * @author nisus
 * @version 0.1
 * @since 2023/5/9 21:17
 */
public class Q_机器人走步 {

    public static void main(String[] args) {
        Judger.of(() -> {
            int N = 10, M = 2, K = 3, P = 3;
            int r1 = new D().func(N, M, K, P);
            int r2 = S1.ways1(N, M, K, P);
            return r1 == r2;
        }).setIterCount(1).start().print();
    }

    static class D {

        int func(int n, int m, int k, int p) {
            int res = func0(n, m, k, p, m, 0);
            return res;
        }

        private int func0(int N, int M, int K, int P, int i, int step) {
            if (step > K || i < 0 || i >= N) {
                return 0;
            }
            if (step == K && i == P) {
                // 第 k 步, 且恰好到了 p 点, OK
                return 1;
            }

            return func0(N, M, K, P, i + 1, step + 1)
                    + func0(N, M, K, P, i - 1, step + 1);
        }

    }

    static class S1 {
        public static int ways1(int N, int start, int aim, int K) {
            if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
                return -1;
            }
            return process1(start, K, aim, N);
        }

        // 机器人当前来到的位置是cur，
        // 机器人还有rest步需要去走，
        // 最终的目标是aim，
        // 有哪些位置？1~N
        // 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
        public static int process1(int cur, int rest, int aim, int N) {
            if (rest == 0) { // 如果已经不需要走了，走完了！
                return cur == aim ? 1 : 0;
            }
            // (cur, rest)
            if (cur == 1) { // 1 -> 2
                return process1(2, rest - 1, aim, N);
            }
            // (cur, rest)
            if (cur == N) { // N-1 <- N
                return process1(N - 1, rest - 1, aim, N);
            }
            // (cur, rest)
            return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
        }
    }


}
